#include <stdio.h>

//#define STDIN
//#define DEBUG

int t;
int M, N;

int compute_k(int m, int n)
{
#ifdef DEBUG
    printf("%d %d\n", m, n);
#endif
    if (m == 1 || m == 0 || n == 1 || n == 0)
        return 1;
    else if (m >= n)
        return compute_k(m-n, n) + compute_k(m, n-1);
    else if (m < n)
        return compute_k(m, m);
    else
        return 0;
}

int main()
{
#ifdef STDIN
    freopen("bin/1664.in", "r", stdin);
#endif

    int i;
    scanf("%d", &t);
    for (i = 0; i < t; ++i)
    {
        scanf("%d %d", &M, &N);
        printf("%d\n", compute_k(M, N));
    }
   return 0; 
}
